\documentclass[E:/GsjzTle/main/main.tex]{subfiles}
\begin{document}

复杂度\textbf{\(O(MlogM+Mlog(M))\)}

\begin{itemize}
\item
  \(sum\) 为最小生成树的权值和 （得到 \(sum\) 之前要先 \(work\) ！)
\item
  假设现在要把一条非树边 \((u,v,c)\)
  加入最小生成树，想必要去掉一条原生成树中 \(u->v\)
  的边，显然去掉最大边效果是最好的
\item
  所以在最小生成树上跑一个倍增\(DP\)，\(d[i][j]\) 表示 \(j\) 的 \(2^i\)
  次祖先到 \(j\) 的路径中最大的值
\item
  然后再枚举每一条非树边 \(vis[i] = 0\) , 然后再取 \(min\) 就好
\end{itemize}

\begin{lstlisting}
const int N = 3e5 + 10 , INF = 0x3f3f3f3f3f3f3f3fll;
struct node
{
	int w, u, v, id, vis;
	bool operator < (const node& A) const
	{
		return w < A.w;
	}
} edge[N];
struct Edge
{
	int nex, to, w;
} e[N << 1];
int head[N], TOT;

int dep[N] , fa[N][23] , f1[N][23] , f2[N][23];  // f1 维护最大值 , f2 维护次大值 
vector<int> G[N];
void add_edge(int u, int v, int w)
{
	e[++TOT].nex = head[u];
	e[TOT].to = v;
	head[u] = TOT;
	e[TOT].w = w;
}
void dfs(int u,int far)
{
	dep[u] = dep[far] + 1;
	fa[u][0] = far;
	for (int i = 1; (1 << i) <= dep[u]; i++)
	{
		fa[u][i] = fa[fa[u][i-1]][i-1];
		f1[u][i] = max(f1[u][i - 1], f1[fa[u][i - 1]][i - 1]);
		if (f1[u][i - 1] == f1[fa[u][i - 1]][i - 1])
		f2[u][i] = max(f2[u][i - 1], f2[fa[u][i - 1]][i - 1]);
	}
	for (int i = head[u]; i ; i = e[i].nex)
	{
		int v = e[i].to, w = e[i].w;
		if (v == far) continue;
		f1[v][0] = w;
		dfs(v,u);
	}
}
int lca(int u,int v)
{
	if (dep[u] < dep[v]) swap(u,v);
	for(int i = 22; i >= 0; i--)
	{
		if (dep[fa[u][i]] >= dep[v])
		{
			u = fa[u][i];
		}
	}
	if (u == v) return u;
	for(int i = 22; i >= 0; i--)
	{
		if (fa[u][i] != fa[v][i])
		{
			u = fa[u][i];
			v = fa[v][i];
		}
	}
	return fa[u][0];
}
int get_max(int x, int y, int w)
{
	//	w = -INF;   	//取消注释则求非严格次小生成树
	int res = 0;
	for (int i = 22; i >= 0; i--)
	{
		if (dep[fa[x][i]] >= dep[y])
		{
			res = max(res, f1[x][i] == w ? f2[x][i]:f1[x][i]); // 防止次小生成树 = 最小生成树 
			x = fa[x][i];
		}
	}
	return res;
}
int far[N] , mst , ans[N];
int find(int x)
{
	if (far[x] == x) return x;
	return far[x] = find(far[x]);
}
void init()
{
	for(int i = 1 ; i <= N - 10 ; i ++) far[i] = i , G[i].clear();
}
signed main()
{
	init();
	int n, m;
	cin >> n >> m;
	for (int i = 1; i <= m; i++)
	{
		int u, v, w;
		cin >> u >> v >> w;
		edge[i] = {w,u,v,i,0};
	}
	sort(edge + 1, edge + 1 + m);
	for (int i = 1; i <= n; i++) far[i] = i;
	for (int i = 1; i <= m; i++)
	{
		int x = edge[i].u, y = edge[i].v, w = edge[i].w;
		int tx = find(x), ty = find(y);
		if (tx != ty)
		{
			far[tx] = ty;
			add_edge(x, y, w);
			add_edge(y, x, w);
			mst += w;
			edge[i].vis = 1;
		}
	}
	dfs(1,0);
	int sum = INF;
	for (int i = 1; i <= m; i++)
	{
		if (edge[i].vis) continue;
		int x = edge[i].u, y = edge[i].v, w = edge[i].w;
		int z = lca(x, y);
		int d = max(get_max(x, z, w), get_max(y, z, w));
		sum = min(sum, mst - d + w);
	}
	cout << sum << '\n';
	return 0;
}
\end{lstlisting}

\end{document}
